#ifndef FENTREE_H_INCLUDED
#define FENTREE_H_INCLUDED

#include<cstdlib>
#include<vector>
#include<cstddef>

template<typename dataType>
class fenTree
{
private:
    std::vector<dataType> data;

    size_t fenUp(size_t x) const
    {
        return x | (x + 1);
    }
    ptrdiff_t fenDown(ptrdiff_t x) const
    {
        return (x & (x + 1)) - 1;
    }
public:
    fenTree(size_t n)
    {
        data.resize(n);
    }
	void inc(size_t x, dataType value)
	{
        size_t i = x;
        while (i < data.size())
        {
            data[i] = data[i] + value;
            i = fenUp(i);
        }
	}

	dataType sumFromZero(size_t x) const
	{
	    dataType sumIn = 0;
        ptrdiff_t i = x - 1;
        while (i >= 0)
        {
            sumIn = sumIn + data[i];
            i = fenDown(i);
        }
        return sumIn;
	}

	dataType sum(size_t x1, size_t x2) const
	{
	    return sumFromZero(x2) - sumFromZero(x1);
	}
};

#endif // FENTREE_H_INCLUDED
